package com.algorithm.graph;

import java.util.*;

/**
 * 有向图 最短路径
 * https://blog.csdn.net/qq_44957574/article/details/119120300?spm=1001.2014.3001.5502
 */
public class DirectedGraphMinRoute {

    HashMap<String, String> parent;
    HashSet<String> bests;
    int[] distance;

    public DirectedGraphMinRoute(int len){
        parent = new HashMap<>(); // key: 当前节点，value：从原点到达key的最短路径的前驱节点
        distance = new int[len]; // distance[i]: 原节点到节点i的最短距离
        bests = new HashSet<>(); // 选择过的最优的节点的集合
    }

    //通过node名称获取node下标
    public int getNodeIndex(String[] nodes, String nodeName){
        for(int i=0;i<nodes.length;i++){
            if(nodes[i].equals(nodeName)){
                return i;
            }
        }
        return -1;
    }

    public void print(int[][] weights){
        for(int i=0;i<weights.length;i++){
            int[] weight = weights[i];
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int j=0;j<weight.length;j++){
                list.add(weight[j]);
            }
            System.out.println(list);
        }
    }
    public int getMinNum(int[][] weights, List<Integer> nodeIndexList){
        //System.out.println(nodeIndexList);
        //print(weights);
        int num = 0;
        for(int i=0;i<nodeIndexList.size();i++){
            int j = i+1;
            if(j>=nodeIndexList.size()){
                break;
            }
            num+=weights[nodeIndexList.get(i)][nodeIndexList.get(j)];
        }
        return num;
    }

    public void dijkstra(int[][] weights, String[] nodes, int startIndex){
        // 1. 初始化：源点到自身距离为0，到其他节点距离为无穷大
        for(int i=0;i<nodes.length;i++){
            if(i==startIndex-1)
                this.distance[i] = 0;
            else this.distance[i] = Integer.MAX_VALUE;
        }
        // 不断迭代
        while (true){
            int min = Integer.MAX_VALUE;
            int index = -1;
            // 1. 在未标记的节点中找出从源点到该点最短的路径节点
            for(int i=0;i<this.distance.length;i++){
                if(this.distance[i] < min && !bests.contains(nodes[i])){
                    min = this.distance[i];
                    index = i;
                }
            }
            // 找不到可达的路径了
            if(index == -1){
                break;
            }
            // 将该节点放入bests集合中
            this.bests.add(nodes[index]);
            // 2. 扩展该节点的子节点，计算源点到子节点的距离，若小于原来距离，则更新
            // distance表和parent表
            for(int i=0;i<nodes.length;i++){
                // 找到一个为扩展的子节点
                if(weights[index][i]>0 && !bests.contains(nodes[i])){
                    int new_dis = distance[index] + weights[index][i];
                    // 新距离小于原始距离，更新
                    if(new_dis < distance[i]){
                        distance[i] = new_dis;
                        parent.put(nodes[i], nodes[index]);
                    }
                }
            }
        }
        // 倒叙找到路径
        for(int i=0;i<nodes.length;i++){
            if(i != startIndex-1){
                if(this.distance[i] == Integer.MAX_VALUE){
                    //System.out.print(nodes[v-1]+"到"+nodes[i]+"之间没有最短路径");
                    continue;
                }else {
                    ArrayList<String> path = new ArrayList<>();
                    String current = nodes[i];
                    path.add(current);
                    while (current != nodes[startIndex-1]){
                        current = parent.get(current);
                        path.add(current);
                    }

                    List<Integer> nodeIndexList = new ArrayList<>();
                    for(int j=path.size()-1;j>=0;j--){
                        nodeIndexList.add(getNodeIndex(nodes,path.get(j)));
                        if(j!=0)
                            System.out.print(path.get(j)+"->");
                        else System.out.print(path.get(j));
                    }
                    int minNum = getMinNum(weights, nodeIndexList);
                    System.out.print(" " + minNum);
                }
                System.out.println();
            }

        }
    }
    public static void main(String[] args){
        int[][] weight= {
                {0,5,7,-1,-1,-1, 2},
                {-1,0,-1,9,-1,-1,3},
                {-1,-1,0,-1,8,-1,-1},
                {-1,-1,-1,0,-1,4,-1},
                {-1,-1,-1,-1,0,-1,-1},
                {-1,-1,-1,4,5,0,-1},
                {-1,-1,-1,-1,4,6,0}
        };
        String[] str= {"A","B","C","D","E","F","G"};
        int len=str.length;
        DirectedGraphMinRoute p1 = new DirectedGraphMinRoute(len);
        p1.dijkstra(weight, str, 1);
    }
}
